#include <queue>
#include "utils.h"
using namespace std;

class Solution {
public:
    bool hasPathSum(TreeNode *root, int sum) {
        if (root == NULL) return false;
        int diff = sum - root->val;
        if (root->left==NULL && root->right==NULL) return (!diff);
        return ((root->left!=NULL && hasPathSum(root->left, diff)) ||
                (root->right!=NULL && hasPathSum(root->right, diff)));
    }

    bool hasPathSum_iterator(TreeNode *root, int sum) {
        if (root == NULL) return false;

        queue<TreeNode*> q;
        queue<int> sum_q;
        int path_sum;
        q.push(root);
        sum_q.push(root->val);

        while(!q.empty()) {
            TreeNode *p = q.front();
            q.pop();
            path_sum = sum_q.front();
            sum_q.pop();

            // determine if the path sum is equal to sum in leaf
            if (p->left == NULL && p->right == NULL && path_sum == sum) return true;

            if (p->left != NULL) {
                q.push(p->left);
                sum_q.push(p->left->val + path_sum);
            }
            if (p->right != NULL) {
                q.push(p->right);
                sum_q.push(p->right->val + path_sum);
            }
        }
        return false;
    }
};

int main(int argc, char *argv[])
{
    int a[] = {5, 4, 8, 11, -1, 13, 4, 7, 2, -1, -1, 5, 1};
    vector<int> v(a, a+sizeof(a)/sizeof(int));
    TreeNode *root = build_binary_tree(v);
    print_vector(levelOrder(root));

    Solution ss;
    int sum = 22;
    cout << ss.hasPathSum(root, sum) <<endl;
    cout << ss.hasPathSum_iterator(root, sum) << endl;

    return 0;
}
